import java.util.LinkedList;
import java.util.Queue;

/**
 *240. 搜索二维矩阵 II
 * https://leetcode.cn/problems/search-a-2d-matrix-ii/description/
 */
class Solution {
    int n, m;
    int[] dx = {0, 1};//右，下
    int[] dy = {1, 0};
    boolean[][] vist;

    public boolean searchMatrix(int[][] matrix, int target) {
        m = matrix.length;
        n = matrix[0].length;
        vist = new boolean[m][n];
        return bfs(matrix, target);
    }

    public boolean bfs(int[][] matrix, int target) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        vist[0][0] = true;

        while (!q.isEmpty()) {
            int[] t = q.poll();
            int a = t[0], b = t[1];
            int tmp = matrix[a][b];
            if(tmp == target) return true;
            if (tmp < target) {
                //向右和向下寻找
                for (int i = 0; i < 2; i++) {
                    int x = dx[i] + a;
                    int y = dy[i] + b;
                    if (x >= 0 && x < m && y >= 0 && y < n && !vist[x][y]) {
                        q.add(new int[]{x, y});
                        vist[x][y] = true;
                    }
                }
            }
        }

        return false;
    }
}